//
// Created by user on 2022/4/25.
//
#include <vector>
#include <algorithm>
using namespace std;
class CompleteKnapsack{
public:
    //动态规划思路
    //dp[i][c]：将[0..i]号物品放入容量为c的背包中产生的最大价值
    //int[][] dp=new int[w.length][C+1]
    //状态转移： 不放 dp[i][j] = dp[i-1][c] c<w[i]
    //           放 dp[i][j] = max(dp[i-1][c], k*v[i]+dp[i-1][c-k*w[i]]) c>=w[i] k\in [0, c/w[i]] bug
                             //max(dp[i][c], k*v[i]+dp[i-1][c-k*w[i]]) c>=w[i] k\in [0, c/w[i]]
    int complete_knapsack(vector<int> &w, vector<int> &v, int C){
        
        //定义维度
        vector<vector<int>> dp(w.size(), vector<int>(C+1));
        
        //初始化
        for (int c = 0; c <= C; ++c) {
            dp[0][c] = (c/w[0])*v[0];
        }

        for (int i = 1; i <w.size() ; ++i) {
            for (int j = 0; j <=C ; ++j) {
                int count = j/w[i];
                for (int k = 0; k <=count ; ++k) {
                    dp[i][j] = max(dp[i][j], k*v[i]+dp[i-1][j-k*w[i]]);
                }

            }
        }
        return dp[w.size()-1][C];
    }


    //空间优化
    int complete_knapsack1(vector<int> &w, vector<int> &v, int C){

        //定义维度
        vector<int> dp(C+1);

        //初始化
        for (int c = 0; c <= C; ++c) {
            dp[c] = (c/w[0])*v[0];
        }

        for (int i = 1; i <w.size() ; ++i) {
            for (int j = 0; j <=C ; ++j) {
                int count = j/w[i];
                for (int k = 0; k <=count ; ++k) {
                    dp[j] = max(dp[j], k*v[i]+dp[j-k*w[i]]);
                }
            }
        }
        return dp[C];
    }
};